package a_doubleWrite;

/**
 * 547. 省份数量
 * 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，
 * 且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
 * <p>
 * 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
 *
 * @author: luolidong
 * @create: 2021-07-23 10:13
 * @version: 1.0
 */
public class L547 {
    /**
     * todo
     *
     * @param M M相当于无向图的连接矩阵,求连通域的个数
     * @return int
     */
    public int findCircleNum(int[][] M) {
        if (M.length == 1) return 1;
        int count = 0;
        int len = M.length;
        boolean[] visited = new boolean[len];
        //行列都是相同的，只需遍历一次
        for (int i = 0; i < M.length; i++) {
            if (!visited[i]) {
                dfs(M, visited, i);
                count++;
            }
        }
        return count;
    }

    public void dfs(int[][] nums, boolean[] visited, int i) {
        visited[i] = true;//访问后置为true
        for (int j = 0; j < nums.length; j++) {
            if (nums[i][j] == 1 && !visited[j]) {
                dfs(nums, visited, j);//如果是连接的，继续遍历它的连接节点
            }
        }
    }
}
